//一个单向链表中删除倒数第K个节点
//参考资料：
//http://blog.csdn.net/csdn_cwj/article/details/51523992
//https://zhuanlan.zhihu.com/p/33010759?group_id=936872081623949312


public class RemoveLastKthNode {
    // 在单链表中删除倒数第k个节点(方法一)
    public static ListNode removeLastKthNode1(ListNode head, int k) {
        //不删除节点或者链表为空
        if ((k <= 0) || (head == null)) {
            return head;
        }
        ListNode p = head;
        //k的值大于链表长度，则不用删除
        for (int i = 0; i < k; i++) {
            if (p.nextNode != null) {
                p = p.nextNode;
            } else {
                return head;
            }
        }
        //k的值小于链表长度，则删除链表中的某个节点
        ListNode q = head;
        while (p.nextNode != null) {
            p = p.nextNode;
            q = q.nextNode;
        }
        q.nextNode = q.nextNode.nextNode;
        return head;
    }

    // 2.在单链表中删除倒数第k个节点(方法二)
    public static ListNode removeLastKthNode2(ListNode head, int k) {
        //不删除节点或者链表为空
        if((k <= 0) || (head == null)) {
            return head;
        }
        ListNode p = head;
        while(p != null){
            p = p.nextNode;
            k--;
        }
        //k的值等于链表长度，则删除头结点
        if(k==0) {
            return head.nextNode;
        }
        //k的值小于链表长度，则删除链表中的某个节点
        if(k<0){
            ListNode q = head;
            while(++k!=0){ //这里注意，先自加，在判断
                q=q.nextNode;
            }
            q.nextNode=q.nextNode.nextNode;
        }
        return head;
    }
    // 创建链表
    public static ListNode createListNode(int data[]) {
        ListNode head = new ListNode(data[0]);
        ListNode temp = head;
        for (int i = 1; i < data.length; i++) {
            ListNode headNext = new ListNode(data[i]);
            temp.nextNode = headNext;
            temp = temp.nextNode;
        }
        return head;
    }

    // 测试个方法
    public static void main(String[] args) {
        int[] data1 = { 1, 2, 4, 5, 6, 7 };
        ListNode h1 = createListNode(data1);
        //在单链表中删除倒数第k个节点
        ListNode head1 = removeLastKthNode1(h1, 3);
        System.out.println("使用第一种方法：");
        while (head1 != null) {
            System.out.println(head1.values);
            head1 = head1.nextNode;
        }
        System.out.println();
        int[] data2 = { 1, 2, 4, 5, 6, 7 };
        ListNode h2 = createListNode(data2);
        //在单链表中删除倒数第k个节点
        ListNode head2 = removeLastKthNode2(h2, 2);
        System.out.println("使用第二种方法：");
        while (head2 != null) {
            System.out.println(head2.values);
            head2 = head2.nextNode;
        }
    }
}

